<!DOCTYPE html>
<!--[if lt IE 7]> <html class="no-js lt-ie9 lt-ie8 lt-ie7"> <![endif]-->
<!--[if IE 7]> <html class="no-js lt-ie9 lt-ie8"> <![endif]-->
<!--[if IE 8]> <html class="no-js lt-ie9"> <![endif]-->
<!--[if gt IE 8]><!--> <html class="no-js"> <!--<![endif]-->
<head>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <title>Raft -- Understandable Distributed Consensus  &middot; 骚铭科技的博客（建设中）</title>
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="viewport" content="width=device-width, initial-scale=1">


<meta name="description" content="Raft 是一个便于理解的一致性算法(Consensus algorithm)，在此之前，最为著名的就是 Paxos 算法。很多一致性算法都是基于paxos的，但说实话，paxos真特么难以理解，看来看去只能看懂算法流程，无法理解为什么work。而Raft 要好理解的多。看动画演示可以理解大致算法流程和如何容错，具体细节可以看 Raft 论文。" />

<meta name="keywords" content="分布式系统, ">


<meta property="og:title" content="Raft -- Understandable Distributed Consensus  &middot; 骚铭科技的博客（建设中） ">
<meta property="og:site_name" content="骚铭科技的博客（建设中）"/>
<meta property="og:url" content="http://yunyu-mr.github.io/cloud/raft/" />
<meta property="og:locale" content="en-EN">


<meta property="og:type" content="article" />
<meta property="og:description" content="Raft 是一个便于理解的一致性算法(Consensus algorithm)，在此之前，最为著名的就是 Paxos 算法。很多一致性算法都是基于paxos的，但说实话，paxos真特么难以理解，看来看去只能看懂算法流程，无法理解为什么work。而Raft 要好理解的多。看动画演示可以理解大致算法流程和如何容错，具体细节可以看 Raft 论文。"/>
<meta property="og:article:published_time" content="2016-07-08T09:59:36&#43;08:00" />
<meta property="og:article:modified_time" content="2016-07-08T09:59:36&#43;08:00" />

  
    
<meta property="og:article:tag" content="分布式系统">
    
  

  

<script type="application/ld+json">
  {
    "@context": "http://schema.org",
    "@type": "Article",
    "headline": "Raft -- Understandable Distributed Consensus",
    "author": {
      "@type": "Person",
      "name": "http://profiles.google.com/+?rel=author"
    },
    "datePublished": "2016-07-08",
    "description": "Raft 是一个便于理解的一致性算法(Consensus algorithm)，在此之前，最为著名的就是 Paxos 算法。很多一致性算法都是基于paxos的，但说实话，paxos真特么难以理解，看来看去只能看懂算法流程，无法理解为什么work。而Raft 要好理解的多。看动画演示可以理解大致算法流程和如何容错，具体细节可以看 Raft 论文。",
    "wordCount":  512 
  }
</script>



<link rel="canonical" href="http://yunyu-mr.github.io/cloud/raft/" />

<link rel="apple-touch-icon-precomposed" sizes="144x144" href="http://yunyu-mr.github.io/touch-icon-144-precomposed.png">
<link href="http://yunyu-mr.github.io/favicon.png" rel="icon">
<meta name="theme-color" content="#2053AB">
<meta name="generator" content="Hugo 0.15" />

  <!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
<script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->

<link href='https://fonts.googleapis.com/css?family=Merriweather:300%7CRaleway%7COpen+Sans' rel='stylesheet' type='text/css'>
<link rel="stylesheet" href="http://yunyu-mr.github.io/css/font-awesome.min.css">
<link rel="stylesheet" href="http://yunyu-mr.github.io/css/style.css">
<link rel="stylesheet" href="http://yunyu-mr.github.io/css/highlight/default.css">

  
</head>
<body>
  <main id="main-wrapper" class="container main_wrapper has-sidebar">
    <header id="main-header" class="container main_header">
  <div id="profile">
<a class="baselink" href="http://yunyu-mr.github.io/">
	<div class="portrait" itemprop="image" style="background-image: url('http://yunyu-mr.github.io/img/smtech.jpeg');"></div>
	</div>
</a>
<br>

<div class="container brand">
  <div class="container title h1-like">
  <a class="baselink" href="http://yunyu-mr.github.io/">
  ♂骚铭科技

</a>

</div>

  
<div class="container topline">
  
  交流交流，学习学习


</div>


</div>
  <nav class="container nav primary no-print">
  

<a class="homelink" href="http://yunyu-mr.github.io/">首页</a>


  
<a href="http://yunyu-mr.github.io/about">关于</a>

<a href="http://yunyu-mr.github.io/cloud" title="学术">学术</a>

<a href="http://yunyu-mr.github.io/post" title="文章列表">文章</a>

<a href="http://yunyu-mr.github.io/topics" title="Show list of topics">分类</a>


</nav>

<div class="container nav secondary no-print">
  
<a id="contact-link-email" class="contact_link" href="mailto:yourname@example.com">
  <span class="fa fa-envelope-square"></span><span>email</span></a>



<a id="contact-link-github" class="contact_link" href="https://github.com/yunyu-Mr">
  <span class="fa fa-github-square"></span><span>github</span></a>



<a id="contact-link-bitbucket" class="contact_link" href="https://bitbucket.org/yunyu-Mr">
  <span class="fa fa-bitbucket-square"></span><span>bitbucket</span></a>















</div>


  

</header>


<article id="main-content" class="container main_content single">
  <header class="container hat">
  <h1>Raft -- Understandable Distributed Consensus
</h1>

  <div class="metas">
<time datetime="2016-07-08">8 Jul, 2016</time>


  
    &middot; by author
  
  &middot; Read in about 3 min
  &middot; (512 Words)
  <br>
  
<a class="label" href="http://yunyu-mr.github.io/tags/%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F">分布式系统</a>



</div>

</header>

  <div class="container content">
  

<h2 id="简介:767c52fb6a9e0737d07fe04e0bf0fd9c">简介</h2>

<p>​   Raft 是一个便于理解的一致性算法(Consensus algorithm)，在此之前，最为著名的就是 Paxos 算法。很多一致性算法都是基于paxos的，但说实话，paxos真特么难以理解，看来看去只能看懂算法流程，无法理解为什么work。而Raft 要好理解的多。看动画演示可以理解大致算法流程和如何容错，具体细节可以看 Raft 论文。</p>

<p>​   <a href="thesecretlivesofdata.com/raft/">动画演示</a></p>

<p>​   <a href="http://nil.csail.mit.edu/6.824/2016/papers/raft-extended.pdf">Raft paper</a></p>

<p>​   文章中对一致性算法的定义我觉得不错:</p>

<blockquote>
<p>​ Consensus algorithms allow a collection of machines to work as a coherent group that can survive the fail-ures of some of its members.</p>
</blockquote>

<p>​   一致性算法使得一个<strong>机群</strong>可以像一个协同相关的<strong>小组</strong>一样工作，即使在某些机器挂掉的情况下也能正常工作。</p>

<h3 id="关键问题-如何避免大脑分裂-split-brain:767c52fb6a9e0737d07fe04e0bf0fd9c">关键问题：如何避免大脑分裂（split brain）?</h3>

<p>要避免大脑分裂，需要避免两个问题：</p>

<ol>
<li>Crashed：即使某个member挂了，整个机群仍然可以正常工作，也即容错。</li>
<li>Partition：即使机群因为通信异常被分成两份，仍然可以工作，也即可以避免网络分割。</li>
</ol>

<h2 id="状态机:767c52fb6a9e0737d07fe04e0bf0fd9c">状态机</h2>

<h2 id="算法流程:767c52fb6a9e0737d07fe04e0bf0fd9c">算法流程</h2>

<p>Raft 主要有两个步骤：</p>

<ul>
<li>选举：Leader election</li>
<li>复制：Log replication</li>
</ul>

<p>每个 member 可能有三种角色（状态）：</p>

<ul>
<li>Leader</li>
<li>Candidate</li>
<li>Follower</li>
</ul>

<h3 id="leader-election:767c52fb6a9e0737d07fe04e0bf0fd9c">Leader Election</h3>

<p>Raft 中Leader的思想跟Paxos算法中的有点相似，第一步都是要确定一个Leader。那么怎么选举呢？这里涉及两个超时：election timeout 跟 vote timeout。</p>

<p>首先，选举超时的 follower 会变成 candidate，然后他就会发送 RequestVote 请求。</p>

<p>然后，进入选举模式，该 candidate 等待 大部分（majority）成员的响应。如果等了很久都没反应，这时投票超时，candidate 会再次发起选举请求；如果大部分成员及时回复Ok，那么candidate 就变成 leader。</p>

<p>选出 leader 后，它必须周期性地发送 heartbeat 保持存在感。只要心跳及时回复，leader 就一直保持领导地位。一旦任意一个 follower 选举超时，就会重新选举。</p>

<h3 id="log-replication:767c52fb6a9e0737d07fe04e0bf0fd9c">Log Replication</h3>

<p>Client 把指令发给 leader， leader 负责备份指令。</p>

<p>首先，client 将指令发给 leader，leader 把指令写入自己的 log 序列中。</p>

<p>然后，leader 向 follower 发送 AppendEntry 请求（其实就是加在心跳中）。Follower 收到请求后，将指令写入自己的 log 序列中，并回复Ok。</p>

<p>最后，如果 leader 得到大部分成员的通过，他就会将指令写入<strong>状态机</strong>中，并回复 client。随后，leader 还要告诉其他 follower 也把刚才的指令写入状态机中；如果 leader 得不到部分成员的通过，他是不会将指令加入状态机的，也就是说这条指令没有大部分成员的通过，是不会最终执行的。</p>

<h2 id="课程问题:767c52fb6a9e0737d07fe04e0bf0fd9c">课程问题</h2>

<h4 id="when-does-raft-start-a-leader-election:767c52fb6a9e0737d07fe04e0bf0fd9c">When does Raft start a leader election?</h4>

<ol>
<li>如果 follower 在election timeout 时间内没有收到 heartbeat，那么他就会变成 candidate，并发起选举。</li>
<li>如果candidate 发出选举请求后，在限定投票时间内没收到足够多的票数，他会再次发起选举。</li>
</ol>

<h4 id="how-to-ensure-at-most-one-leader-in-a-term:767c52fb6a9e0737d07fe04e0bf0fd9c">How to ensure at most one leader in a term?</h4>

<p>前提：</p>

<ul>
<li>只有得到大部分成员（majority）的票数才能成为leader。</li>
<li>每个 follower 在每个 term 期间只能投一次票。</li>
</ul>

<p>所以，在每个 term 期间，最多只有一个 leader 可以得到大部分成员的票数。</p>

<h4 id="how-does-a-server-know-that-election-succeeded:767c52fb6a9e0737d07fe04e0bf0fd9c">How does a server know that election succeeded?</h4>

<ul>
<li>Candidate 获取 majority 票数时，他就知道自己获胜了。</li>
<li>Follower 收到 AppendEntries 心跳时，他就知道新 leader 产生了。</li>
</ul>

<h4 id="an-election-may-not-succeed:767c52fb6a9e0737d07fe04e0bf0fd9c">An election may not succeed？</h4>

<p>如果有<strong>大于3个</strong> candidate 同时发起选举，那么是不可能产生 leader 的。不过这种情况出现的概率实在是太低啦！因为Raft 的超时时间是随机产生的，产生三个相同的随机数，你说概率低不低？</p>

<h4 id="what-happens-after-a-failed-election:767c52fb6a9e0737d07fe04e0bf0fd9c">What happens after a failed election?</h4>

<p>重新选呗！等待另一个 follower 超时，currentTerm ++，变成 candidate。currentTerm 越大则越新，老的 candidate 会被淘汰（不选他）。</p>

<h4 id="how-does-raft-reduce-chances-of-election-failure-due-to-split-vote:767c52fb6a9e0737d07fe04e0bf0fd9c">How does Raft reduce chances of election failure due to split vote?</h4>

<p>正如上面所说，Raft 的超时时间是<strong>随机</strong>产生的，所以多个 candidate 同时超时然后发起选举的概率是非常低的。还有，根据论文<strong>5.6小节</strong>，时间上还要满足下面这个时间条件：</p>

<blockquote>
<p><strong>broadcastTime ≪ electionTimeout ≪ MTBF</strong></p>
</blockquote>

<p>广播时间必须远远小于选举超时，否则如果两个超时随机数比较接近也不行，容易出现二次选举（前一次没完成，第二个超时又产生了）。</p>

<h4 id="how-to-choose-the-random-delay-range:767c52fb6a9e0737d07fe04e0bf0fd9c">How to choose the random delay range?</h4>

<p>太短：容易产生二次选举（如上所述，前一次选举没完成，第二个超时又来了）。</p>

<p>太长：等待时间太长，浪费了，效率低。</p>

<h4 id="what-if-old-leader-isn-t-aware-a-new-one-is-elected:767c52fb6a9e0737d07fe04e0bf0fd9c">What if old leader isn&rsquo;t aware a new one is elected?</h4>

<p>就算老 Leader 不知道新 leader 已经被选，也不影响大局。因为 majority 已经选择了新 leader，老leader 已被抛弃。即使老leader继续发 AppendEntries，也只有 minority 会回复ok，majority 是会拒绝他的，也就是说他的 log 不会写入状态机。</p>

<p>内部分歧，但不会造成&raquo;人格分裂“。</p>

<hr />

<p>下面谈谈在出现错误之后，如何同步日志</p>

<h4 id="what-do-we-want-to-ensure:767c52fb6a9e0737d07fe04e0bf0fd9c">What do we want to ensure?</h4>

<p>我们希望每个server 执行的命令都相同，顺序相同，也即他们的状态是一致的。详见论文Fig.3</p>

<blockquote>
<p><strong>State Machine Safety</strong>: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index.</p>
</blockquote>

<h4 id="how-can-logs-disagree:767c52fb6a9e0737d07fe04e0bf0fd9c">How can logs disagree?</h4>

<p>日志不同的情况有两种：</p>

<ol>
<li>缺失。</li>
</ol>

<p>s0: 3</p>

<p>s1: 3, 3, 3</p>

<p>s2: 3, 3, 3</p>

<ol>
<li>错乱。</li>
</ol>

<p>s0: 3</p>

<p>s1: 3, 3, 4</p>

<p>s2: 3, 3, 5</p>

<h4 id="new-leader-will-force-its-log-on-followers:767c52fb6a9e0737d07fe04e0bf0fd9c">New leader will force its log on followers</h4>

<p>New leader 会先找到跟 followers 匹配的logs，然后将后面不匹配的全部删掉，并将logs补齐。</p>

<h4 id="could-new-leader-roll-back-executed-entries-from-end-of-previous-term:767c52fb6a9e0737d07fe04e0bf0fd9c">Could new leader roll back <em>executed</em> entries from end of previous term?</h4>

<p>不可以，一旦执行是不能撤销的！否则将违反状态机安全性原则(state machine safty）。Raft 为了保证这一点，选举的新 leader 的日志里必须包含全部已经提交的记录（entries）。</p>

<blockquote>
<p>Raft uses the voting process to prevent a candidate fromwinning an election unless its log contains all committedentries.</p>
</blockquote>

<h4 id="could-we-choose-leader-with-longest-log:767c52fb6a9e0737d07fe04e0bf0fd9c">Could we choose leader with longest log?</h4>

<pre><code>  example:
    S1: 5 6 7
    S2: 5 8
    S3: 5 8
</code></pre>

<p>即使 S1 有最长的日志，但他是不可能被选中的，因为他还停留在 term 7。而 S2 和 S3 已经到 term 8 了。所以，新 leader 只会在 S2和 S3中产生，选择包含最长日志的 candidate 是不科学的。</p>

<h4 id="please-explained-at-least-as-up-to-date-voting-rules:767c52fb6a9e0737d07fe04e0bf0fd9c">Please explained ”<em>At least as up to date</em>&raquo; voting rules?</h4>

<ol>
<li>优先选择有最新的日期（terms）候选者。</li>
<li>如果记录中最新的terms 都相同，则优先选择日志长的候选者。</li>
</ol>

<blockquote>
<p>If the logs have last entries with different terms, thenthe log with the later term is more up-to-date.</p>

<p>If the logs end with the same term, then whichever log is longer ismore up-to-date.</p>
</blockquote>

<hr />

<p>下面谈谈配置更改的问题</p>

<h4 id="why-doesn-t-a-straightforward-approach-work:767c52fb6a9e0737d07fe04e0bf0fd9c">Why doesn&rsquo;t a straightforward approach work?</h4>

<p>下面这张图表示增加两个servers：S4, S5。也就是从3节点 -&gt; 5节点。</p>

<p><img src="/img/raft-reconfiguration.png" alt="raft-reconfiguration" /></p>

<p>由于收到新配置的时间不同，会出现下面这个时刻：</p>

<ul>
<li>S1, S2 用旧配置（3个节点），那么，S1 可能会被选为leader（只需要S1,S2同意）；</li>
<li>S3, S4, S5 使用新配置（5个节点），那么，S5 可能会被选为leader（只需要S3,S4,S5同意）。</li>
</ul>

<p>结果可能导致这个时刻出现两个 leader，显然，大脑分裂了！</p>

<h4 id="raft-configuration-change-how:767c52fb6a9e0737d07fe04e0bf0fd9c">Raft configuration change. How?</h4>

<p>思路：增加一个过渡阶段 “joint consensus”，同时包含旧配置$C_{old}$和新配置$C_{new}$（过渡配置：$C_{old,new}$）。</p>

<p>步骤：</p>

<ol>
<li>Leader 收到更改配置请求后，将$C_{old,new}$弄成一条日志记录（log entry），然后同步它。</li>
<li>一旦$C_{old,new}$被提交，$C_{old}$就不再使用了，当然，$C_{new}$也不会使用。这保证了过渡时期的安全。随后，$C_{new}$会被发送。</li>
<li>$C_{new}$被提交后，配置就更改成功了。</li>
</ol>

<p>容错：</p>

<ul>
<li>如果发生崩溃，而新leader 还没收到 $C_{old,new}$，那么他会继续使用$C_{old}$，并没什么影响。</li>
<li>如果崩溃后新选举的leader 已经有$C_{old,new}$记录了，那么他会继续完成配置更改。</li>
</ul>

<h2 id="疑问:767c52fb6a9e0737d07fe04e0bf0fd9c">疑问</h2>

<ul>
<li>以前听云计算课程，一般replica 的数目为<strong>3</strong>个或<strong>5</strong>个。而在Raft中，一个cluster 是没有限定数目的，如果我的集群有100台集群，岂不是有100个replicas？这不科学吧，太浪费了。再说，如果面对超大规模的文件，如何处理？</li>
</ul>

<p>​My answer: Raft 是一致性协议，是为了使所有机器的操作保持一致，而不是用于备份文件。</p>

</div>


  <footer class="container">
  <div class="container navigation no-print">
  <h2>Navigation</h2>
  
  


</div>

  <div class="container comments">
  <h2>Comments</h2>
  



<div id="uyan_frame"></div>
<script type="text/javascript" src="http://v2.uyan.cc/code/uyan.js?uid=2106103"></script>




</div>

</footer>

</article>
      <footer id="main-footer" class="container main_footer">
  

  <div class="container nav foot no-print">
  

  <a class="toplink" href="#">back to top</a>

</div>

  <div class="container credits">
  
<div class="container footline">
  
  code with <i class='fa fa-heart'></i>


</div>


  
<div class="container copyright">
  
  &copy; 2016 骚铭科技 SM-Tech!.


</div>


</div>

</footer>

    </main>
    
<script type="text/javascript">
  (function() {
    
    
    if (window.location.hostname == "localhost")
      return;

    var dsq = document.createElement('script'); dsq.async = true; dsq.type = 'text/javascript';
    dsq.src = '//smtech.disqus.com/count.js';
    (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq);
  })();
</script>



<script src="http://yunyu-mr.github.io/js/highlight.pack.js"></script>
<script>hljs.initHighlightingOnLoad();</script>



<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'Your Google Analytics tracking code', 'auto');
  ga('send', 'pageview');

</script>


    
  </body>
</html>

<script type="text/javascript"
  src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
  tex2jax: {
    inlineMath: [['$','$'], ['\\(','\\)']],
    displayMath: [['$$','$$'], ['\[','\]']],
    processEscapes: true,
    processEnvironments: true,
    skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'],
    TeX: { equationNumbers: { autoNumber: "AMS" },
         extensions: ["AMSmath.js", "AMSsymbols.js"] }
  }
});
</script>

<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    
    
    
    var all = MathJax.Hub.getAllJax(), i;
    for(i = 0; i < all.length; i += 1) {
        all[i].SourceElement().parentNode.className += ' has-jax';
    }
});
</script>
